package _算法._数学问题;

import java.util.Scanner;

/***
问题形式
        　　
 有n个位置1...n，每个位置上有ai个石子。有两个人轮流操作。操作步骤是：挑选1...n中任一一个存在石子的位置i，将至少1个石子移动
 至i−1位置（也就是最后所有石子都堆在在0这个位置）。谁不能操作谁输。求先手必胜还是必败。
        　　　　

    结论
        　　
  问题等价于，求位置为奇数的ai的异或和，若异或和等于0，则先手必败，否则先手必胜。你可能已经注意到这非常像Nim游戏。其实这个
  游戏恰好等价于：将每个奇数位置的数x看成一堆有x个石子的石子堆，然后玩Nim游戏。


证明
        　　
        　　拿走某一堆石子的一部分，相当于将某个奇位置的石子移动到它左边的偶位置上。
        　　
        　　如果大家都只动奇位置的石子，那么这等价于两人在玩Nim游戏。
        　　
        　　但如果有人想打破规则呢？
        　　
        　　假设Nim游戏先手必胜，那么先手肯定优先玩Nim游戏；如果后手试图破坏局面，将某个偶位置上的若干石子移动到了左边的奇位置i上，那么先手可以将这若干个刚移到i的石子继续移动到i左边的偶位置上，对Nim局面依然没有任何影响，除非后手回头来继续动奇位置的石子，那也只能是输。
        　　
        　　那么如果Nim游戏先手必败，也是同理，后手可以用相同的方式迫使先手玩Nim游戏，直到输为止。
        　　
        　　因此，奇数位置的石子的相关信息，就直接决定了阶梯Nim问题的结果。
***/
public class _阶梯Nim {
    public static void main(String[] args) {

        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        int[] arr = new int[n];
        for (int i = 0; i < n; i++) {
            arr[i] = sc.nextInt();
        }
        int res = 0;
        for (int i = 0; i < n; i += 2) {
            res ^= arr[i];
        }
        System.out.println(res == 0 ? "先手必败" : "先手必胜");
    }
}
/***
变题：

# 问题描述
        # 　　古时丧葬活动中经常请高僧做法事。仪式结束后，有时会有“高僧斗法”的趣味节目，以舒缓压抑的气氛。
        # 　　节目大略步骤为：先用粮食（一般是稻米）在地上“画”出若干级台阶（表示N级浮屠）。又有若干小和尚随机地“站”在某个台阶上。最高一级台阶必须站人，其它任意。(如图1所示)
        # 　　两位参加游戏的法师分别指挥某个小和尚向上走任意多级的台阶，但会被站在高级台阶上的小和尚阻挡，不能越过。两个小和尚也不能站在同一台阶，也不能向低级台阶移动。
        # 　　两法师轮流发出指令，最后所有小和尚必然会都挤在高段台阶，再也不能向上移动。轮到哪个法师指挥时无法继续移动，则游戏结束，该法师认输。
        # 　　对于已知的台阶数和小和尚的分布位置，请你计算先发指令的法师该如何决策才能保证胜出。
        # 输入格式
        # 　　输入数据为一行用空格分开的N个整数，表示小和尚的位置。台阶序号从1算起，所以最后一个小和尚的位置即是台阶的总数。（N<100, 台阶总数<1000）
        # 输出格式
        # 　　输出为一行用空格分开的两个整数: A B, 表示把A位置的小和尚移动到B位置。若有多个解，输出A值较小的解，若无解则输出-1。
        # 样例输入
        # 1 5 9
        # 样例输出
        # 1 4
        # 样例输入
        # 1 5 8 10
        # 样例输出
        # 1 3

   思路：等价于Nim问题，两个和尚的中间空的位置为石头，然后进行Nim游戏 向前走等于拿走任意个石头
    if __name__ == "__main__":
        s = input()
        arr = list(map(eval, s.split()))
        res = 0
        if (len(arr) & 1) == 1:  # 奇数
            for i in range(1, len(arr), 2):
                res ^= 0 if i == len(arr) - 1 else arr[i] - arr[i - 1] - 1

        else:
            for i in range(1, len(arr), 2):
                res ^= arr[i] - arr[i - 1] - 1
        if res == 0:
            print(-1)
        else:
            for j in range(len(arr) - 1):
                res ^= arr[j + 1] - arr[j] - 1
                rmax = arr[j]
                for i in range(arr[j], arr[j + 1]):
                    if ((arr[j + 1] - i - 1) ^ res) == 0 and i > rmax:
                        rmax = i
                    if rmax != arr[j]:
                        print(arr[j], rmax)
                        break

                # 回溯
                res ^= arr[j + 1] - arr[j] - 1
 ***/